package primary.math;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/9
 **/
public class IsPowerOfThree {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int i=1;
        while(i > 0){
            list.add(i);
            i*=3;
        }
        for (Integer integer : list) {
            System.out.print(+integer+",");
        }
    }
    /*
        解法一，依次判定x = 1，3，9，……是否为n，当x>n时停止,时间复杂度O（logn)
        注意避免i溢出
     */
    public boolean isPowerOfThree(int n){
        boolean ans = false;
        for (int i = 1; i <= n && i > 0; i*=3) {
            if(i == n){
                ans = true;
            }
        }
        return ans;
    }

    /*
        解法二：打表
     */
    static final int[] powerOfThrees = new int[]{1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467};
    public boolean isPowerOfThree2(int n){
        for (int i = 0; i < powerOfThrees.length; i++) {
            if(powerOfThrees[i]==n)
                return true;
        }
        return false;
    }
    /*
        解法三：
        题中n的范围是-2^31 <= n <= 2^31 - 1，而在这个范围内3的最大幂是1162261467，在比他大就超过int表示的范围了，我们直接用它对n求余即可，过求余的结果是0，说明n是3的幂次方

     */
    public boolean isPowerOfThree3(int n) {
        return (n > 0 && 1162261467 % n == 0);
    }

}
